|
|
|
|||||||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Czabarka Éva: Curious crossing critical edges - variations on an example of Siran |
|
|||
|
|
||||
|
||||
| An edge $e$ of the graph $G$ is crossing critical if its removal decreases the crossing number of the graph, i.e. $cr(G-e) Kuratowski theorem states that a graph is nonplanar precisely when it contains a subdivision of a $K_5$ or a $K_{3,3}$. Subgraphs that are subdivided $K_5$ or subdivided $K_{3,3}$ are Kuratowski subgraphs, an edge is a Kuratowski edge if it is in a Kuratowski subgraph, and a Kuratowski edge is a strong Kuratowski edge if it is in every Kuratowski subgraph. Kuratowski theorem implies that strong Kuratowski edges are crossing-critical. We consider the following questions: If an edge is crossed in every optimal drawing of the graph, is it a Kuratowski edge? If an edge is a strong Kuratowski edge, is it crossed in some optimal drawing of the graph? If an edge is not a Kuratowski edge and is not crossed in any optimal drawing, can it be crossing critical? This is joint work with Alec Helm. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013
