Simple Topological Drawings of k-Planar Graphs and Planarization Approaches
Explore the concepts of simple topological drawings in k-planar graphs, planarity, crossing numbers, and planarization approaches. Learn about the maximum crossings per edge, local crossing numbers, and the relationship between total crossings and minimizing maximum crossings. Discover insights on 4-planar graphs and the idea of rerouting edges, as well as discussions on bounding crossing numbers and improving bounds for k-planar graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Simple Topological Drawings of k-planar Graphs Authors: Chih-Hung Liu, Meghana M. Reddy, Csaba D. T th Meghana M. Reddy meghana.mreddy@inf.ethz.ch D-INFK, ETH Z rich March 16, 2020 1
Planarity of a graph Maximum #crossings per edge k-planar graph: has a drawing with at most k crossings per edge local crossing number K4: planar K5: 1-planar K7: 2-planar 2
Crossing number of a graph Total #crossings in a drawing Graph crossing number 3
Simple Topological Drawings Any two edges have at most one point in common. X X Simple local crossing number local crossing number vs simple local crossing number For k-planar graphs, and , minimizing total crossings also minimizes the maximum crossings per edge (Pach et al., 2006). However, the same is not true for(Schaefer, 2018). 4
Simple drawings of k-planar graphs Does a 4-planar graph always have a 3290-plane simple topological drawing? Does there exist a function such that every k-planar graph has an -plane simple drawing? (Question by Schaefer) Yes! 5
Idea: Rerouting the edges Lens Arcs 6
Planarization approach 2 Network N Combinatorial length of an edge <= 2 Elimination/rerouting of lens: Length of the arcs Number of crossings 5 3 Maximum crossings per edge is bounded! 2 0 Crossings in a small neighborhood of a node of N. 7
Planarization approach Edges passing through node : Number of vertices incident to the edges <= + Bounded number of nodes = Bounded #crossings! 8
Conclusion The simple local crossing number can be bounded by a function of the local crossing number. for k-planar graph. Can the bounds be further improved? Lower bound? For k = 4? Thank you! 9
