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. Journal articles
  4. Saturated simple and k-simple topological graphs
 
research article

Saturated simple and k-simple topological graphs

Kyncl, Jan  
•
Pach, Janos  
•
Radoicic, Rados
Show more
2015
Computational Geometry-Theory And Applications

A simple topological graph G is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. G is called saturated if no further edge can be added without violating this condition. We construct saturated simple topological graphs with n vertices and O(n) edges. For every k > 1, we give similar constructions for k-simple topological graphs, that is, for graphs drawn in the plane so that any two edges have at most k points in common. We show that in any k-simple topological graph, any two independent vertices can be connected by a curve that crosses each of the original edges at most 2k times. Another construction shows that the bound 2k cannot be improved. Several other related problems are also considered. (C) 2014 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.comgeo.2014.10.008
Web of Science ID

WOS:000348960100001

Author(s)
Kyncl, Jan  
Pach, Janos  
Radoicic, Rados
Toth, Geza
Date Issued

2015

Publisher

Elsevier Science Bv

Published in
Computational Geometry-Theory And Applications
Volume

48

Issue

4

Start page

295

End page

310

Subjects

Simple topological graph

•

Saturated topological graph

•

Pseudoline arrangement

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
May 29, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/114232
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