On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
dc.contributor.author
Felsner, Stefan
dc.contributor.author
Hoffmann, Michael
dc.contributor.author
Knorr, Kristin
dc.contributor.author
Parada, Irene
dc.contributor.editor
Auber, David
dc.contributor.editor
Valtr, Pavel
dc.date.accessioned
2021-02-19T13:38:46Z
dc.date.available
2021-01-22T20:11:27Z
dc.date.available
2021-02-19T13:38:46Z
dc.date.issued
2020
dc.identifier.isbn
978-3-030-68765-6
en_US
dc.identifier.isbn
978-3-030-68766-3
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-68766-3_30
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/465000
dc.description.abstract
A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of Kn with no empty lens. In this setting we prove an upper bound of 3((n−4)!) on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by n!.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.subject
Star-simple drawings
en_US
dc.subject
Topological graphs
en_US
dc.subject
Edge crossings
en_US
dc.title
On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
en_US
dc.type
Conference Paper
dc.date.published
2021-02-14
ethz.book.title
Graph Drawing and Network Visualization
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
12590
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
382
en_US
ethz.pages.end
389
en_US
ethz.event
28th International Symposium on Graph Drawing and Network Visualization (GD 2020) (virtual)
en_US
ethz.event.location
Vancouver, Canada
en_US
ethz.event.date
September 16-18, 2020
en_US
ethz.notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually
en_US
ethz.grant
Arrangements and Drawings (ArrDra)
en_US
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.grant.agreementno
171681
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2021-01-22T20:11:44Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-02-19T13:38:57Z
ethz.rosetta.lastUpdated
2022-03-29T05:19:16Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=On%20the%20Maximum%20Number%20of%20Crossings%20in%20Star-Simple%20Drawings%20of%20Kn%20with%20No%20Empty%20Lens&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2020&rft.volume=12590&rft.spage=382&rft.epage=389&rft.issn=0302-9743&1611-3349&rft.au=Felsner,%20Stefan&Hoffmann,%20Michael&Knorr,%20Kristin&Parada,%20Irene&rft.isbn=978-3-030-68765-6&978-3-030-68766-3&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-68766-3_30&rft.btitle=Graph%20Drawing%20and%20Network%20Visualization
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Conference Paper [33089]