# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Drawing Planar Graphs on Points Inside a Polygon

and Floderus, Peter LU (2012) 37th International Symposium, MFSC 2012 In Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012) 7464. p.172-183
Abstract
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.
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Graph drawing, Specified point set, Bounding polygon
in
Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012)
editor
; ; and
volume
7464
pages
11 pages
publisher
Springer
conference name
37th International Symposium, MFSC 2012
external identifiers
• scopus:84865034932
ISSN
0302-9743
1611-3349
ISBN
978-3-642-32589-2
978-3-642-32588-5
DOI
10.1007/978-3-642-32589-2_18
language
English
LU publication?
yes
id
f4fc71f5-e906-4692-94fb-7a467835be08 (old id 7867589)
2016-01-20 17:01:54
date last changed
2018-01-07 03:40:26
```@inproceedings{f4fc71f5-e906-4692-94fb-7a467835be08,
abstract     = {In this paper, we study the problem of drawing a given planar<br/><br>
graph such that vertices are at pre-specified points and the<br/><br>
entire drawing is inside a given polygon. We give a method that shows that for<br/><br>
an \$n\$-vertex graph and a \$k\$-sided polygon, \$\Theta(kn^2)\$ bends<br/><br>
are always sufficient. We also give an example of a graph where <br/><br>
\$\Theta(kn^2)\$ bends is necessary for such a drawing.},
author       = {Biedl, Therese and Floderus, Peter},
booktitle    = {Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012)},
editor       = {Rovan, Branislav and Sassone, Vladimiro and Widmayer, Peter},
isbn         = {978-3-642-32589-2},
issn         = {0302-9743},
keyword      = {Graph drawing,Specified point set,Bounding polygon},
language     = {eng},
pages        = {172--183},
publisher    = {Springer},
title        = {Drawing Planar Graphs on Points Inside a Polygon},
url          = {http://dx.doi.org/10.1007/978-3-642-32589-2_18},
volume       = {7464},
year         = {2012},
}

```