On the number of edges of fan-crossing free graphs

Otfried Cheong, Sariel Har-Peled, Heuna Kim, Hyo Sil Kim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A graph drawn in the plane with n vertices is fan-crossing free if there is no triple of edges e,f and g, such that e and f have a common endpoint and g crosses both e and f. We prove a tight bound of 4n - 9 on the maximum number of edges of such a graph for a straight-edge drawing. The bound is 4n - 8 if the edges are Jordan curves. We also discuss generalizations to monotone graph properties.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Pages163-173
Number of pages11
DOIs
StatePublished - Dec 1 2013
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: Dec 16 2013Dec 18 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8283 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other24th International Symposium on Algorithms and Computation, ISAAC 2013
CountryChina
CityHong Kong
Period12/16/1312/18/13

    Fingerprint

Keywords

  • extremal graph
  • graph drawing
  • graph theory
  • planar graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Cheong, O., Har-Peled, S., Kim, H., & Kim, H. S. (2013). On the number of edges of fan-crossing free graphs. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings (pp. 163-173). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS). https://doi.org/10.1007/978-3-642-45030-3_16