Advanced

Drawing Planar Graphs on Points Inside a Polygon

Biedl, Therese 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.
Please use this url to cite or link to this publication:
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
Rovan, Branislav; Sassone, Vladimiro; Widmayer, Peter; ; 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)
date added to LUP
2016-01-20 17:01:54
date last changed
2017-01-01 03:25:37
@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},
}