Two-planar graphs are quasiplanar
OPEN ACCESS
Author / Producer
Date
2017
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Abstract
It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross.
Permanent link
Publication status
published
External links
Editor
Book title
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Volume
83
Pages / Article No.
47
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
graph drawing; near-planar graph; simple topological plane graph
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)