Untangling a planar graph

A. Spillner, A. Wolff

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)


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.
Originele taal-2Engels
TitelSOFSEM 2008 : Theory and Practice of Computer Science (Proceedings 34th Conference, Nový Smokovec, Slovakia, January 19-25, 2008)
RedacteurenV. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková
Plaats van productieBerlin
ISBN van geprinte versie978-3-540-77565-2
StatusGepubliceerd - 2008

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Untangling a planar graph'. Samen vormen ze een unieke vingerafdruk.

Citeer dit