Results 51 to 60 of about 433,943 (319)
The structure of 1-planar graphs
Discrete Mathematics, 2007 AbstractA graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an
Igor Fabrici, Tomáš Madaras
openaire +2 more sources
Computational Study on a PTAS for Planar Dominating Set Problem
Algorithms, 2013 The dominating set problem is a core NP-hard problem in combinatorial optimization and graph theory, and has many important applications. Baker [JACM 41,1994] introduces a k-outer planar graph decomposition-based framework for designing polynomial time ...
Qian-Ping Gu, Marjan Marzban
doaj +1 more source
A note on odd colorings of 1-planar graphs
Discrete Applied Mathematics, 2023 A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. This notion was recently introduced by Petruševski and Škrekovski, who proved that every planar graph admits an odd $9$-coloring; they also conjectured that every planar graph admits an odd $5$-coloring. Shortly after,
Cranston, Daniel W. +2 more
openaire +2 more sources
An annotated bibliography on 1-planarity [PDF]
, 2017 The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge.
Kobourov, Stephen G. +2 more
core +1 more source
Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs [PDF]
, 2013 A graph is called a strong (resp. weak) bar 1-visibility graph if its vertices can be represented as horizontal segments (bars) in the plane so that its edges are all (resp.
William J. Evans +5 more
openalex +4 more sources
About Structure of Graph Obstructions for Klein Surface with 9 Vertices
Кібернетика та комп'ютерні технології, 2020 The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of (-transformations of the graphs.
V.I. Petrenjuk, D.A. Petrenjuk
doaj +1 more source
1-Bend RAC Drawings of 1-Planar Graphs [PDF]
International Symposium Graph Drawing and Network Visualization, 2016 A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles.
W. Didimo +3 more
semanticscholar +1 more source
Dynamic list coloring of 1-planar graphs [PDF]
Discrete Mathematics, 2021 A graph is $k$-planar if it can be drawn in the plane so that each edge is crossed at most $k$ times. Typically, the class of 1-planar graphs is among the most investigated graph families within the so-called "beyond planar graphs". A dynamic $\ell$-list coloring of a graph is a proper coloring so that each vertex receives a color from a list of $\ell$
Xin Zhang, Yan Li
openaire +3 more sources
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs [PDF]
, 2014 Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a ...
A. Grigoriev +19 more
core +1 more source