Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [planar-graphs]

The tag has no usage guidance.

1
vote
1answer
69 views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
6
votes
1answer
154 views

Does Max Planar 3-SAT admit a PTAS?

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
3
votes
1answer
65 views

NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049 For a problem I'm ...
6
votes
0answers
67 views

Fáry-Like Theorems for nonplanar graphs

Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane. In general the edges of $G$ may be represented as ...
2
votes
0answers
37 views

Min cut problem on unbalanced partitions for planar graphs with unit capacity edges

The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
7
votes
1answer
123 views

Another planar separator ref question

Do any of you know a reference for the following (surprisingly tedious to prove) result? Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \...
3
votes
1answer
108 views

Finding a “lowest” path in a graph

I have an undirected graph $G = (E,V)$, $|V|=n$, where each node $v_i$ has a natural number weight. Think of these weights as heights $h_i$. Given two nodes $s$ and $t$, I'd like to find a lowest ...
0
votes
0answers
21 views

is there any result on mTSP over highly structured/modular graphs?

I am looking for theoretical results on mTSP (multiple travelling salesmen problem) over structured/modular graphs. If the meaning of "modular" is not clear, think about a graph that represents a ...
1
vote
0answers
35 views

Planarity testing of directed graph and 3d grid

I wonder if there exist definitions (and known algorithms) of planarity testing for the following case: 1- A directed graph let $G=(V=\{1,\ldots,n\},E)$ be a directed graph. Assume $e_{ij} =(v_i,...
4
votes
1answer
174 views

How hard is it to determine the chromatic number of a unit distance graph?

For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?
3
votes
0answers
108 views

Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$. The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-...
5
votes
2answers
220 views

Efficient way to generate random planar cubic bipartite graphs

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
1
vote
0answers
73 views

Counting the number of connected components in a dynamic plane graph

I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{...
5
votes
0answers
120 views

reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected ...
1
vote
1answer
238 views

Making planar graph biconnected

I've given a planar graph (with clockwise ordering of vertices). I would like to make it biconnected by adding some number of edges. Graph should remain planar, of course. How can I do this? Few more ...
2
votes
0answers
67 views

Describe the condition of “non-adjacent 3-cycles” in terms of the cubic adjacency matrix

Oleg Borodin and André Raspaud "A sufficient condition for planar graphs to be 3-colorable" Journal of Combinatorial Theory B88, 2003, 17–27 state the following conjecture: Conjecture 1.2: ...
2
votes
0answers
81 views

What can i learn about a graph about which only certain properties are known [closed]

1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts? The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable, The degree of each ...
4
votes
1answer
107 views

Shortest cycle separator for biconnected planar graphs

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is ...
4
votes
1answer
621 views

Smallest vertex cover which is also an independent set

The vertex cover and independent set as a subset of nodes are always considered in a dual relationship. Have they been looked at together? What I mean is: start from a minimum vertex cover, and if it ...
1
vote
1answer
82 views

Subclasses or characterizations of modular or pseudo-modular planar graphs

We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined ...
0
votes
2answers
322 views

Efficient algorithm for testing planarity of the union of two planar graphs

Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs. Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar? That is, an algorithm more efficient than ...
3
votes
1answer
296 views

Graph planarity testing via adjacency matrix

I have looked at several efficient graph planarity algorithms which rely on computing and traversing DFS trees (that add one vertex/edge/path at a time). I am looking for graph planarity algorithms ...
1
vote
0answers
138 views

Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region /...
2
votes
0answers
444 views

Shortest non-crossing geometric paths

I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
7
votes
0answers
72 views

How much is known about coloring of planar graphs with degree bounds?

Are there any references that address the following (open?) questions: 1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time? 2) What is the largest ...
5
votes
1answer
283 views

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
5
votes
2answers
164 views

Book Embedding Duality of Graphs

The definition of Book Embedding on Wikipedia: "A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as ...
11
votes
0answers
116 views

s-t connectivity on infinite planar graphs with finite description

I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, more ...
15
votes
2answers
1k views

Time complexity of counting triangles in planar graphs

Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward ...
7
votes
0answers
144 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
4
votes
1answer
150 views

Addding edges to spanning tree without destroying planarity

Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ ...
13
votes
1answer
467 views

“Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
1
vote
4answers
1k views

Finding outer face in plane graph (embedded planar graph)

I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices. Computing a ...
4
votes
0answers
59 views

On simultaneous embeddings with different vertex sets

The topic of simultaneous embeddings of planar graphs is a common sight in the recent graph drawing literature. A recent survey of the topic is given by Bläsius, Kobourov and Ritter. I am interested ...
2
votes
1answer
448 views

Planar separator theorem and tree decomposition

The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an $\...
7
votes
2answers
838 views

Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for 4-...
8
votes
1answer
571 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
5
votes
0answers
56 views

Interpolating the Tutte polynomial at the values of two hyperbolas

In a MO question basically I asked when the Tutte polynomial of planar graph can be uniquely determined by the polynomially computable values at the special points and at the two hyperbolas. The ...
28
votes
4answers
2k views

What is simplest polynomial algorithm for PLANARITY?

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
10
votes
0answers
283 views

A bijection between ordered lambda terms and rooted planar maps?

Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{...
4
votes
1answer
156 views

Dual Barnette's Conjecture

Is every Eulerian triangulated (planar) graph Hamiltonian? On the other hand we have that: Barnette's Conjecture (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian. Notice ...
0
votes
1answer
82 views

Number of $k$-cuts of grid graphs

Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$. Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on ...
-4
votes
1answer
261 views

How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4? [closed]

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph. We can choose two non-adjacent vertices a,b and contract them into a single vertex. If ...
10
votes
4answers
744 views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

A planar graph is a graph which can be embedded in the plane, without having crossing edges. Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k. ...
4
votes
1answer
134 views

Generalizations of planar graphs that include hypercubes with large side length in $R^d$

A lot of people have asked about generalizations of planar graphs on other forums. Some topics include: https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs https://math....
7
votes
1answer
572 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
5
votes
1answer
466 views

Chromatic number of planar graph with girth at least k

The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones. Girth is ...
8
votes
4answers
1k views

Partitioning graphs while minimizing inter-partition edges

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
1
vote
0answers
58 views

Partition planar graph of vertices with at most degree 3 into connected subgraphs

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...
0
votes
0answers
346 views

Rectangular constraints in Delaunay Triangulation without edges within

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...