Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Hanani-Tutte and Monotone Drawings
 
conference paper

Hanani-Tutte and Monotone Drawings

Fulek, Radoslav  
•
Pelsmajer, Michael J.  
•
Schaefer, Marcus
Show more
Kolman, P
•
Kratochvil, J
2011
Graph-Theoretic Concepts In Computer Science
37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011)

A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Toth showed that if a graph has an x-monotone drawing in which every pair of edges crosses an even number of times, then the graph has an x-monotone embedding in which the x-coordinates of all vertices are unchanged. We give a new proof of this result and strengthen it by showing that the conclusion remains true even if adjacent edges are allowed to cross oddly. This answers a question posed by Pach and Toth. Moreover, we show that an extension of this result for graphs with non-adjacent pairs of edges crossing oddly fails even if there exists only one such pair in a graph.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-25870-1_26
Web of Science ID

WOS:000307088100026

Author(s)
Fulek, Radoslav  
Pelsmajer, Michael J.  
Schaefer, Marcus
Stefankovic, Daniel
Editors
Kolman, P
•
Kratochvil, J
Date Issued

2011

Publisher

Springer-Verlag Berlin

Publisher place

Berlin

Published in
Graph-Theoretic Concepts In Computer Science
ISBN of the book

978-3-642-25869-5

Total of pages

12

Series title/Series vol.

Lecture Notes in Computer Science; 6986

Start page

283

End page

294

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent placeEvent date
37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011)

Tepla Monastery, CZECH REPUBLIC

JUN 21-24, 2011

Available on Infoscience
February 28, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/90009
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés