On the Number of Edges of Fan-Crossing Free Graphs

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

doi:10.1007/s00453-014-9935-z

On the Number of Edges of Fan-Crossing Free Graphs

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A graph drawn in the plane with n vertices is -fan-crossing free for geqslant if there are no edges,e1,…,ek, such that ldots …,ek have a common endpoint and crosses all We prove a tight bound of on the maximum number of edges of a -fan-crossing free graph, and a tight bound for a straight-edge drawing. For geqslant we prove an upper bound of (k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.

Original language	English (US)
Pages (from-to)	673-695
Number of pages	23
Journal	Algorithmica
Volume	73
Issue number	4
DOIs	https://doi.org/10.1007/s00453-014-9935-z
State	Published - Dec 1 2015

Keywords

Crossing number
Graph drawing
K-planar graphs

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-014-9935-z

Library availability

Discover UIUC Full Text

Cite this

@article{b81f9b549de441299dc9959f2d4b8458,

title = "On the Number of Edges of Fan-Crossing Free Graphs",

abstract = "A graph drawn in the plane with n vertices is -fan-crossing free for geqslant if there are no edges,e1,…,ek, such that ldots …,ek have a common endpoint and crosses all We prove a tight bound of on the maximum number of edges of a -fan-crossing free graph, and a tight bound for a straight-edge drawing. For geqslant we prove an upper bound of (k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.",

keywords = "Crossing number, Graph drawing, K-planar graphs",

author = "Otfried Cheong and Sariel Har-Peled and Heuna Kim and Kim, {Hyo Sil}",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = dec,

day = "1",

doi = "10.1007/s00453-014-9935-z",

language = "English (US)",

volume = "73",

pages = "673--695",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - On the Number of Edges of Fan-Crossing Free Graphs

AU - Cheong, Otfried

AU - Har-Peled, Sariel

AU - Kim, Heuna

AU - Kim, Hyo Sil

PY - 2015/12/1

Y1 - 2015/12/1

N2 - A graph drawn in the plane with n vertices is -fan-crossing free for geqslant if there are no edges,e1,…,ek, such that ldots …,ek have a common endpoint and crosses all We prove a tight bound of on the maximum number of edges of a -fan-crossing free graph, and a tight bound for a straight-edge drawing. For geqslant we prove an upper bound of (k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.

AB - A graph drawn in the plane with n vertices is -fan-crossing free for geqslant if there are no edges,e1,…,ek, such that ldots …,ek have a common endpoint and crosses all We prove a tight bound of on the maximum number of edges of a -fan-crossing free graph, and a tight bound for a straight-edge drawing. For geqslant we prove an upper bound of (k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.

KW - Crossing number

KW - Graph drawing

KW - K-planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85027920419&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027920419&partnerID=8YFLogxK

U2 - 10.1007/s00453-014-9935-z

DO - 10.1007/s00453-014-9935-z

M3 - Article

AN - SCOPUS:85027920419

VL - 73

SP - 673

EP - 695

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

IS - 4

ER -

On the Number of Edges of Fan-Crossing Free Graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this