@inproceedings{dd7219eada1a41109b811389193123e2,
title = "β-Stars or On Extending a Drawing of a Connected Subgraph",
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].",
author = "Tamara Mchedlidze and J{\'e}r{\^o}me Urhausen",
year = "2018",
month = dec,
day = "18",
doi = "10.1007/978-3-030-04414-5_30",
language = "English",
isbn = "978-3-030-04413-8",
series = "Lecture Notes in Computer Science ",
publisher = "Springer",
pages = "416--429",
editor = "Therese Biedl and Andreas Kerren",
booktitle = "Graph Drawing and Network Visualization",
edition = "1",
}