We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Crossing numbers

Formale Metadaten

Titel
Crossing numbers
Serientitel
Anzahl der Teile
24
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
One of the most useful tools in topological graph theory is the so-called Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi (1982) and Leighton (1983). It states, roughly speaking, that if a graph drawn in the plane has much more edges than vertices, then the number of crossings between its edges is much larger than the number of edges. We extend this result to simple topological multigraphs, that is, for multigraphs drawn in the plane such that (1) any two independent edges meet in at most one point, (2) no two edges that share an endpoint have any interior point in common, and (3) both lenses enclosed by two edges that have the same endpoint contain at least one vertex in their interiors.
Schlagwörter