Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Note on IC-Planar Graphs
79
0
0.0
(
0
)
Added by
Kathrin Hanauer
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. IC-planarity specializes both NIC-planarity, which allows a pair of crossing edges to share at most one vertex, and 1-planarity, where each edge may be crossed at most once. We show that there are infinitely maximal IC-planar graphs with n vertices and 3n-5 edges and thereby prove a tight lower bound on the density of this class of graphs.
rate research
Read More
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end 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 per edge. We characterize embeddings of maximal NIC-planar graphs in terms of generalized planar dual graphs. The characterization is used to derive tight bounds on the density of maximal NIC-planar graphs which ranges between 3.2(n-2) and 3.6(n-2). Further, we prove that optimal NIC-planar graphs with 3.6(n-2) edges have a unique embedding and can be recognized in linear time, whereas the general recognition problem of NIC-planar graphs is NP-complete. In addition, we show that there are NIC-planar graphs that do not admit right angle crossing drawings, which distinguishes NIC-planar from IC-planar graphs.
In this short note, we show two NP-completeness results regarding the emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some $k$ graphs can be represented so that every vertex is represented by the same interval in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when $k$ is a part of the input and graphs are not in a sunflower position.
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source $s$ and a destination $t$, find the smallest subset of vertices whose intersection with any $s-t$ path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelles theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph $G$ contains a cactus subgraph $C$ where $C$ contains at least a $frac{1}{6}$ fraction of the triangular faces of $G$. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing dense planar structures inside any graph: (i) A $frac{1}{6}$ approximation algorithm for, given any graph $G$, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous $frac{1}{11}$-approximation; (ii) An alternate (and arguably more illustrative) proof of the $frac{4}{9}$ approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
