β-Stars or On Extending a Drawing of a Connected Subgraph

Tamara Mchedlidze, Jérôme Urhausen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problem of extending the drawing of a subgraph of a given plane graph to a drawing of the entire graph using straight-line and polyline edges. We define the notion of star complexity of a polygon and show that a drawing Γ_H of an induced connected subgraph H can be extended with at most min{h/2, β+log_2(h)+1} bends per edge, where β is the largest star complexity of a face of Γ_H and h is the size of the largest face of H. This result significantly improves the previously known upper bound of 72|V(H)| [5] for the case where H is connected. We also show that our bound is worst case optimal up to a small additive constant. Additionally, we provide an indication of complexity of the problem of testing whether a star-shaped inner face can be extended to a straight-line drawing of the graph; this is in contrast to the fact that the same problem is solvable in linear time for the case of star-shaped outer face [9] and convex inner face [12].
Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization
Subtitle of host publication26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings
EditorsTherese Biedl, Andreas Kerren
Place of PublicationCham
PublisherSpringer
Pages416-429
Number of pages14
Edition1
ISBN (Electronic)978-3-030-04414-5
ISBN (Print)978-3-030-04413-8
DOIs
Publication statusPublished - 18 Dec 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11282
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'β-Stars or On Extending a Drawing of a Connected Subgraph'. Together they form a unique fingerprint.

Cite this