Drawing Planar Graphs on Points Inside a Polygon
Författare
Redaktör
- Branislav Rovan
- Vladimiro Sassone
- Peter Widmayer
Summary, in English
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, $\Theta(kn^2)$ bends
are always sufficient. We also give an example of a graph where
$\Theta(kn^2)$ bends is necessary for such a drawing.
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, $\Theta(kn^2)$ bends
are always sufficient. We also give an example of a graph where
$\Theta(kn^2)$ bends is necessary for such a drawing.
Avdelning/ar
Publiceringsår
2012
Språk
Engelska
Sidor
172-183
Publikation/Tidskrift/Serie
Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012)
Volym
7464
Fulltext
- Available as PDF - 578 kB
- Download statistics
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Nyckelord
- Graph drawing
- Specified point set
- Bounding polygon
Conference name
37th International Symposium, MFSC 2012
Conference date
2012-08-27 - 2012-08-31
Conference place
Bratislava, Slovakia
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 1611-3349
- ISSN: 0302-9743
- ISBN: 978-3-642-32589-2
- ISBN: 978-3-642-32588-5