Untangling a planar graph

A. Spillner, A. Wolff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

In John Tantalo’s on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping vertices fixed for some absolute constant ? It is known that three vertices can always be kept (if n¿=¿5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows with the size of the graph. More specifically, we give a lower bound of on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight.
Original languageEnglish
Title of host publicationSOFSEM 2008 : Theory and Practice of Computer Science (Proceedings 34th Conference, Nový Smokovec, Slovakia, January 19-25, 2008)
EditorsV. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková
Place of PublicationBerlin
PublisherSpringer
Pages473-484
ISBN (Print)978-3-540-77565-2
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
Volume4910
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Untangling a planar graph'. Together they form a unique fingerprint.

Cite this