- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Crossing numbers
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Crossing numbers Pach, János
Description
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. Joint work with Geza Toth.
Item Metadata
| Title |
Crossing numbers
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-08-22T10:57
|
| Description |
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. Joint work
with Geza Toth.
|
| Extent |
22 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: École Polytechnique Fédérale de Lausanne
|
| Series | |
| Date Available |
2018-04-10
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0365300
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International