On partitioning the edges of 1-plane graphs

DOI10.1016/J.TCS.2016.12.004zbMATH Open1357.05125arXiv1511.07303OpenAlexW2176910815MaRDI QIDQ501676FDOQ501676

Authors: William Lenhart, Giuseppe Liotta, Fabrizio Montecchiani 

Publication date: 9 January 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red-blue edge coloring of an optimal 1-plane graph $G$ partitions the edge set of $G$ into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: $(i)$ Every optimal 1-plane graph has a red-blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. $(ii)$ A red-blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed.

Full work available at URL: https://arxiv.org/abs/1511.07303

Recommendations

• New results on edge partitions of 1-plane graphs
• Edge partitions of optimal 2-plane and 3-plane graphs
• Edge partitions of optimal 2-plane and 3-plane graphs
• On edge colorings of \(1\)-planar graphs
• Edge coloring of \(1\)-planar graphs without intersecting triangles and chordal \(5\)-cycles.

zbMATH Keywords

1-planarityedge partitionsoptimal 1-plane graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graphs drawn with few crossings per edge
• Surfaces, tree-width, clique-minors, and partitions
• The structure of 1-planar graphs
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Density of straight-line 1-planar graph drawings
• Right angle crossing graphs and 1-planarity
• Straight-line grid drawings of 3-connected 1-planar graphs
• Fáry's theorem for 1-planar graphs
• Title not available (Why is that?)
• Rectilinear drawings of graphs
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• On the density of maximal 1-planar graphs
• 1-planarity of graphs with a rotation system
• Algorithms for graphs embeddable with few crossings per edge
• Title not available (Why is that?)
• Acyclic colouring of 1-planar graphs
• Optimal 1-planar graphs which triangulate other surfaces
• Re-embeddings of Maximum 1-Planar Graphs
• Map graphs
• On drawings and decompositions of 1-planar graphs
• A note on 1-planar graphs
• A left-first search algorithm for planar graphs
• Edge partition of planar sraphs into two outerplanar graphs
• Triangulating planar graphs while minimizing the maximum degree
• Outerplanar partitions of planar graphs
• Graphs with forbidden subgraphs
• Height-preserving transformations of planar graph drawings
• On visibility representations of non-planar graphs
• Über 1-optimale Graphen
• Contact representations of graphs in 3D
• Title not available (Why is that?)

Cited In (9)

• Edge partitions of optimal 2-plane and 3-plane graphs
• Edge partitions of optimal 2-plane and 3-plane graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge Partitions and Visibility Representations of 1-planar Graphs
• Finding the closed partition of a planar graph
• On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs
• An annotated bibliography on 1-planarity
• New results on edge partitions of 1-plane graphs

This page was built for publication: On partitioning the edges of 1-plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501676)