Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Drawing Planar Graphs on Points Inside a Polygon

Biedl, Therese and Floderus, Peter LU (2012) 37th International Symposium, MFSC 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
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Graph drawing, Specified point set, Bounding polygon
host publication
Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 2012)
editor
Rovan, Branislav ; Sassone, Vladimiro and Widmayer, Peter
volume
7464
pages
11 pages
publisher
Springer
conference name
37th International Symposium, MFSC 2012
conference location
Bratislava, Slovakia
conference dates
2012-08-27 - 2012-08-31
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-04-01 10:15:59
date last changed
2024-10-07 00:42:57
@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}},
  keywords     = {{Graph drawing; Specified point set; Bounding polygon}},
  language     = {{eng}},
  pages        = {{172--183}},
  publisher    = {{Springer}},
  title        = {{Drawing Planar Graphs on Points Inside a Polygon}},
  url          = {{https://lup.lub.lu.se/search/files/1698574/7867597.pdf}},
  doi          = {{10.1007/978-3-642-32589-2_18}},
  volume       = {{7464}},
  year         = {{2012}},
}