The structure of 1-planar graphs

DOI10.1016/J.DISC.2005.11.056MaRDI QIDQ868353zbMATH OpenOpenAlexFDO

Authors Igor Fabrici, Tomáš Madaras

Publication date 2 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.11.056

zbMATH Keywords

crossinglight graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Light subgraphs in the family of 1-planar graphs with high minimum degree
• On local properties of 1-planar graphs with high minimum degree
• Light edges in 1‐planar graphs
• On properties of maximal 1-planar graphs
• On local structure of 1-planar graphs of minimum degree 5 and girth 4

Cites work

• Ein Sechsfarbenproblem auf der Kugel
• Heavy paths, light stars, and big melons
• scientific article; zbMATH DE number 4135967 (Why is no real title available?)
• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 3734660 (Why is no real title available?)
• scientific article; zbMATH DE number 1943979 (Why is no real title available?)
• scientific article; zbMATH DE number 1396798 (Why is no real title available?)
• Light subgraphs of graphs embedded in the plane. A survey
• On \(3\)-connected plane graphs without triangular faces
• On light cycles in plane triangulations
• On light graphs in 3-connected plane graphs without triangular or quadrangular faces
• On light subgraphs in plane graphs of minimum degree five
• On vertex-degree restricted paths in polyhedral graphs
• Subgraphs with restricted degrees of their vertices in planar 3-connected graphs

Cited in

(only showing first 100 items - show all)

• Optimal 1-planar graphs which triangulate other surfaces
• Triangle-free planar graphs with small independence number
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Characterizing and recognizing 4-map graphs
• Light paths and edges in families of outer-1-planar graphs
• Equitable coloring of three classes of 1-planar graphs
• The matching extendability of optimal 1-planar graphs
• Light subgraphs in the family of 1-planar graphs with high minimum degree
• The structure of plane graphs with independent crossings and its applications to coloring problems
• On edge colorings of \(1\)-planar graphs
• Right angle crossing graphs and 1-planarity
• A structure of 1-planar graph and its applications to coloring problems
• On the sizes of bipartite 1-planar graphs
• Planar graphs having no proper 2-immersions in the plane. I
• The maximal 1-planarity and crossing numbers of graphs
• Crossing lemma for the odd-crossing number
• 1-planar graphs without 4-cycles or 5-cycles are 5-colorable
• An improved upper bound for the acyclic chromatic number of 1-planar graphs
• A note on 1-planar graphs with minimum degree 7
• On \((p, 1)\)-total labelling of some 1-planar graphs
• Re-embedding a 1-plane graph for a straight-line drawing in linear time
• On \((p, 1)\)-total labelling of NIC-planar graphs
• Light edges in 1-planar graphs of minimum degree 3
• Remarks on the joins of 1-planar graphs
• Linear arboricity of NIC-planar graphs
• Light structures in 1-planar graphs with an application to linear 2-arboricity
• \(K_7\)-minors in optimal 1-planar graphs
• An annotated bibliography on 1-planarity
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• An upper bound on the sum of powers of the degrees of simple 1-planar graphs
• Minimal non-1-planar graphs
• On the maximum weight of a dense connected graph of given order and size
• A classification of all 1-Salem graphs
• On properties of maximal 1-planar graphs
• Straight-line grid drawings of 3-connected 1-planar graphs
• On the sum of powers of the degrees of graphs
• Outer 1-planar graphs
• scientific article; zbMATH DE number 6381690 (Why is no real title available?)
• On the maximum weight of a sparse connected graph of given order and size
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• scientific article; zbMATH DE number 5943498 (Why is no real title available?)
• Right angle crossing graphs and 1-planarity
• On local properties of 1-planar graphs with high minimum degree
• Contact representations of graphs in 3D
• On edge colorings of 1-toroidal graphs
• On local structure of 1-planar graphs of minimum degree 5 and girth 4
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• Proper 1-immersions of graphs triangulating the plane
• On drawings and decompositions of 1-planar graphs
• A note on 1-planar graphs
• 1-planarity of complete multipartite graphs
• On edge colorings of 1-planar graphs without adjacent triangles
• Connectivity and planarity of g-noncommuting graph of finite groups
• More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges
• Joins of 1-planar graphs
• A linear-time algorithm for testing outer-1-planarity
• Beyond planar graphs: introduction
• 1-Planar Graphs
• Algorithms for 1-Planar Graphs
• Drawing graph joins in the plane with restrictions on crossings
• On partitioning the edges of 1-plane graphs
• The structure and the list 3-dynamic coloring of outer-1-planar graphs
• The linear 2-arboricity of 1-planar graphs without 3-cycles
• On the Size of Matchings in 1-Planar Graph with High Minimum Degree
• Long cycles and spanning subgraphs of locally maximal 1-planar graphs
• From light edges to strong edge-colouring of 1-planar graphs
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Note on improper coloring of 1-planar graphs.
• scientific article; zbMATH DE number 6794321 (Why is no real title available?)
• 1-planar graphs are odd 13-colorable
• Light edges in 1‐planar graphs
• All 2-planar graphs having the same spanning subgraph
• Maximal 1-plane graphs with dominating vertices
• scientific article; zbMATH DE number 7692359 (Why is no real title available?)
• The maximum matching extendability and factor-criticality of 1-planar graphs
• scientific article; zbMATH DE number 7710057 (Why is no real title available?)
• 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
• The structure and the bondage number of three classes of beyond-planar graphs
• The surviving rate of NIC-planar graphs
• A new note on 1-planar graphs with minimum degree 7
• On (p,1)-total labelling of 1-planar graphs
• Spectral extrema of 1-planar graphs
• Nonrepetitive vertex colorings of graphs
• On restricted matching extension of 1-embeddable graphs in surfaces with small genus
• The vertex arboricity of 1-planar graphs
• The strong chromatic index of 1-planar graphs
• Structural properties of LIC-planar graphs
• List edge and list total coloring of 1-planar graphs
• Acyclic choosability of IC-planar graphs
• The 6-degeneracy of 1-planar graphs
• 4-connected 1-planar chordal graphs are Hamiltonian-connected
• The lower bound of the number of non-crossed edges in local maximal 1-plane graphs
• On (r,c)-constant, planar and circulant graphs
• Linear arboricity of 1-planar graphs
• 1-planar graphs with no 5-cycles are 5-degenerate
• On the pagenumber of 1-planar graphs
• Light edges in 3-connected 2-planar graphs with prescribed minimum degree
• On equitable colorings of sparse graphs
• Complexity of (p, q)-bipartition of planar and 1-planar graphs
• An improved upper bound on the linear 2-arboricity of 1-planar graphs

This page was built for publication: The structure of 1-planar graphs

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