### 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 language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings |

Pages | 163-173 |

Number of pages | 11 |

DOIs | |

State | Published - Dec 1 2013 |

Event | 24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China Duration: Dec 16 2013 → Dec 18 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8283 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 24th International Symposium on Algorithms and Computation, ISAAC 2013 |
---|---|

Country | China |

City | Hong Kong |

Period | 12/16/13 → 12/18/13 |

### Keywords

- extremal graph
- graph drawing
- graph theory
- planar graph

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'On the number of edges of fan-crossing free graphs'. Together they form a unique fingerprint.

## 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