Drawing Planar Graphs on Points Inside a Polygon
Author
Editor
- 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.
Department/s
Publishing year
2012
Language
English
Pages
172-183
Publication/Series
Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012)
Volume
7464
Full text
- Available as PDF - 578 kB
- Download statistics
Document type
Conference paper
Publisher
Springer
Topic
- Computer Science
Keywords
- 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/Other
- ISSN: 1611-3349
- ISSN: 0302-9743
- ISBN: 978-3-642-32589-2
- ISBN: 978-3-642-32588-5