2012 | OriginalPaper | Chapter
Drawing Planar Graphs on Points Inside a Polygon
Authors : Therese Biedl, Peter Floderus
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we study the problem of drawing a given planar graph such that vertices are at pre-specified points and the entire drawing is inside a given polygon. We give a method that shows that for an
n
-vertex graph and a
k
-sided polygon, Θ(
kn
2
) bends are always sufficient. We also give an example of a graph where Θ(
kn
2
) bends are necessary for such a drawing.