Name
Abstract | ||
|---|---|---|
Let $G$ be a graph without loops or multiple edges drawn in the plane. It is shown that, for any $k$, if $G$ has at least $C_k n$ edges and $n$ vertices, then it contains three sets of $k$ edges, such that every edge in any of the sets crosses all edges in the other two sets. Furthermore, two of the three sets can be chosen such that all $k$ edges in the set have a common vertex. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/050623693 | SIAM Journal on Discrete Mathematics |
Keywords | Field | DocType |
c_k n,crossing stars,common vertex,topological graphs,multiple edge | Discrete mathematics,Topology,Combinatorics,Path (graph theory),Multigraph,Vertex (geometry),Cycle graph,Matching (graph theory),Mixed graph,Multiple edges,Mathematics,Topological graph | Journal |
Volume | Issue | ISSN |
21 | 3 | 0895-4801 |
Citations | PageRank | References |
6 | 0.94 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Tardos | 1 | 1261 | 140.58 |
| Géza Tóth | 2 | 581 | 55.60 |