On the Number of Edges of Fan-Crossing Free Graphs

Cited 16 time in webofscience Cited 23 time in scopus
  • Hit : 663
  • Download : 0
A graph drawn in the plane with vertices is -fan-crossing free for if there are no edges , such that 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 , we prove an upper bound of edges. We also discuss generalizations to monotone graph properties.
Publisher
SPRINGER
Issue Date
2015-12
Language
English
Article Type
Article
Keywords

QUASI-PLANAR GRAPHS

Citation

ALGORITHMICA, v.73, no.4, pp.673 - 695

ISSN
0178-4617
DOI
10.1007/s00453-014-9935-z
URI
http://hdl.handle.net/10203/205502
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 16 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0