Results 301 to 310 of about 433,943 (319)
Some of the next articles are maybe not open access.
Light edges in 1‐planar graphs
Journal of Graph Theory, 2022A graph is 1‐planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we prove that every 1‐planar graph G $G$ with minimum degree at least 3 contains an edge x y $xy$ with d G ( x ) ≤ d G ( y ) ${d}_ ...
Juan Liu, Yiqiao Wang, Weifan Wang
semanticscholar +1 more source
Extending Partial 1-Planar Drawings
International Colloquium on Automata, Languages and Programming, 2020Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing.
E. Eiben +4 more
semanticscholar +1 more source
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
International Symposium on Mathematical Foundations of Computer Science, 2020The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph $G$, a connected subgraph $H$ of $G$ and a drawing $\mathcal{H}$ of $H$, the extension
E. Eiben +4 more
semanticscholar +1 more source
Recognizing Optimal 1-Planar Graphs in Linear Time
Algorithmica, 2016A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of 4n-8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts ...
F. Brandenburg
semanticscholar +1 more source
A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
International Workshop on Combinatorial Algorithms, 2018We propose a fixed-parameter tractable algorithm for the \textsc{Max-Cut} problem on embedded 1-planar graphs parameterized by the crossing number $k$ of the given embedding.
Christine Dahn +2 more
semanticscholar +1 more source
Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles
International Symposium Graph Drawing and Network Visualization, 2018We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained by drawings whose vertex and crossing resolution is at least \(\pi /4\). On
Philipp Kindermann +3 more
semanticscholar +1 more source
2020
Topological graph theory discusses, in most cases, graphs embedded in the plane (or other surfaces). For example, such plane graphs are sometimes regarded as the simplest town maps. Now, we consider a town having some pedestrian bridges, which cannot be realized by a plane graph. Its underlying graph can actually be regarded as a 1-plane graph.
openaire +2 more sources
Topological graph theory discusses, in most cases, graphs embedded in the plane (or other surfaces). For example, such plane graphs are sometimes regarded as the simplest town maps. Now, we consider a town having some pedestrian bridges, which cannot be realized by a plane graph. Its underlying graph can actually be regarded as a 1-plane graph.
openaire +2 more sources
Algorithms for 1-Planar Graphs
2020A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. This chapter reviews the algorithmic results on 1-planar graphs. We first review a linear time algorithm for testing maximal 1-planarity of a graph if a rotation system (i.e., the circular ...
openaire +1 more source
The Maximal 1-Planarity and Crossing Numbers of Graphs
Graphs and Combinatorics, 2021A 1-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. Czap and Hudak showed that every 1-planar graph with n vertices has crossing number at most $$n-2$$ .
Zhangdong Ouyang +2 more
openaire +3 more sources
Remarks on the joins of 1-planar graphs
Applied Mathematics and Computation, 2019Abstract A graph is called NIC-planar if it admits a drawing in the plane such that each edge is crossed at most once and two pairs of crossing edges share at most one vertex. NIC-planarity generalizes IC-planarity, which allows a vertex to be incident to at most one crossing edge, and specializes 1-planarity, which only requires at most one crossing
Zhangdong Ouyang, Jun Ge, Yichao Chen
openaire +2 more sources