SpringerLink - Book Chapter

Institutional Login

Welcome!

To use the personalized features of this site, please log in or register.

If you have forgotten your username or password, we can help.

My Menu

Marked Items

Alerts

Order History

Saved Items

All

Favorites


Book Chapter

Drawing Outer-Planar Graphs in
<i>O</i>
(
<i>n</i>
log
<i>n</i>
)Area

Drawing Outer-Planar Graphs in O ( n log n )Area

Book Series	Lecture Notes in Computer Science
Publisher	Springer Berlin / Heidelberg
ISSN	0302-9743 (Print) 1611-3349 (Online)
Volume	Volume 2528/2002
Book	Graph Drawing
DOI	10.1007/3-540-36151-0
Copyright	2002
ISBN	978-3-540-00158-4
DOI	10.1007/3-540-36151-0_6
Pages	133-148
Subject Collection	Computer Science
SpringerLink Date	Tuesday, January 01, 2002

Add to marked items

Add to shopping cart

Add to saved items

Permissions & Reprints

Recommend this chapter

PDF (649.7 KB)

Free Preview

Drawing Outer-Planar Graphs in O(n log n )Area

Therese Biedl⁶

(6)	School of Computer Science, University of Waterloo, ON N2L 3G1 Waterloo, Canada

Abstract

In this paper,we study drawings of outer-planar graphs in various models.We showthat O (n log n )area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes.The question of straight-line grid-drawings of outer- planar graphs in o (n ² )area remains open.

Research supported by NSERC.The author would like to thank Erik Demaine, Henk Meijer,Steve Wismath and the Algorithmic Problem Session Group at the University of Waterloo for inspiring discussions.