Skip to main content

Questions tagged [planar-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
117 views

Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
Hao S's user avatar
  • 228
0 votes
1 answer
56 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
BBK's user avatar
  • 103
1 vote
0 answers
33 views

How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
SZH's user avatar
  • 11
1 vote
0 answers
58 views

Pfaffian orientation algorithm for planar graphs

I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related ...
Soham Chatterjee's user avatar
0 votes
0 answers
60 views

Is there a construction which multiplies and adds spanning trees in Logspace?

I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
Turbo's user avatar
  • 13k
3 votes
0 answers
144 views

On perm+1 and det+1

Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both. ...
Turbo's user avatar
  • 13k
0 votes
0 answers
71 views

What is a combinatorial embedding?

I got a reviewer comment saying that I should consider using combinatorial embeddings rather than idk what I should call what I was doing topological embeddings?. But I'm confused because as far as ...
Hao S's user avatar
  • 228
1 vote
0 answers
67 views

Graphs such that every rotation system admits an embedding on a surface of small genus

Let $G$ be a finite, simple, undirected graph. What conditions on $G$ ensure that every rotation system of $G$ corresponds to a cellular embedding of $G$ on an oriented surface of small genus? (e.g. ...
Cyriac Antony's user avatar
1 vote
0 answers
53 views

Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
Hao S's user avatar
  • 228
4 votes
2 answers
208 views

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
Blanco's user avatar
  • 421
2 votes
1 answer
130 views

Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
a3nm's user avatar
  • 9,547
0 votes
1 answer
139 views

2xn grid graphs from ring graphs via local complementations

(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
Dotman's user avatar
  • 109
2 votes
0 answers
70 views

Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?

Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions? No edge touches vertices other than its end vertices. At any ...
Kirubakaran V K's user avatar
3 votes
1 answer
175 views

On cubic planar graphs with face boundaries of length divisible by 4

All graphs considered here are finite, simple and undirected. Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
Cyriac Antony's user avatar
0 votes
1 answer
95 views

Is a grid graph a vertex-minor of a complete graph? [closed]

Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
AngryLion's user avatar
  • 173
6 votes
1 answer
364 views

Complexity of optimal elimination for a planar tensor network

Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question Suppose we need to sum out variables in a tensor network (a factor graph where each ...
Yaroslav Bulatov's user avatar
2 votes
1 answer
81 views

Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question. An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...
Cyriac Antony's user avatar
0 votes
1 answer
58 views

Planar 4-regular vertex-transitive graphs as system of circles

It is known that every planar 4-regular 3-connected graph $G$ admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles such that the vertices of $G$ ...
Cyriac Antony's user avatar
1 vote
0 answers
122 views

Complexity of counting 3-colourings of planar bounded degree graphs

The following are known: It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1]. For all $d\geq 3$, it is #P-complete to count the number ...
Cyriac Antony's user avatar
3 votes
0 answers
96 views

Number of connected partitions (or labelings) in a grid graph

Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, ...
Djoudjou's user avatar
3 votes
0 answers
206 views

(Integer) Linear Program formulation of planarity?

Q: Is there an efficient (I)LP formulation of planarity? More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize ...
GBathie's user avatar
  • 296
1 vote
0 answers
96 views

Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?

Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers ...
Hao S's user avatar
  • 228
0 votes
0 answers
101 views

How many maximal planar graphs are there?

We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
John S's user avatar
  • 1
2 votes
1 answer
129 views

A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below. Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
Cyriac Antony's user avatar
1 vote
1 answer
139 views

Are there non trivial 2-basis of a 2-connected planar graph?

Based on MacLane's planarity criterion, planar graphs are exactly those that admit a 2-basis. Such basis can be easily obtained considering $|E| - |V| + 1$ of its faces. Denoting those basis as ...
Manuel Dubinsky's user avatar
2 votes
0 answers
79 views

Can the theory of Bidimensionality be applied to weighted instances of a problem?

So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this ...
Hao S's user avatar
  • 228
13 votes
1 answer
420 views

Planarity of planar finite automata intersection

It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it ...
gsv's user avatar
  • 421
1 vote
0 answers
242 views

Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
Giorgio Camerani's user avatar
4 votes
0 answers
169 views

Uniquely 4-colorable Planar Graph Conjecture?

My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
Cyriac Antony's user avatar
6 votes
0 answers
120 views

Enumerating homologies of disjoint paths

I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths. I did not understand how do they re-route the paths through a spanning tree and ...
kishlaya's user avatar
  • 191
4 votes
2 answers
832 views

3-colourability of Eulerian maximal planar graph

The following paragraph is from this answer by David Eppstein (emphasis mine). A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single ...
Cyriac Antony's user avatar
2 votes
1 answer
242 views

Who proved that a triangulation is 3-colourable implies its dual is bipartite

Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent: (i) $...
Cyriac Antony's user avatar
3 votes
0 answers
109 views

Homologous flows on planar graphs

I was reading this paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs". First they describe what are cohomologous functions on a graph. My interpretation of this definition ...
kishlaya's user avatar
  • 191
10 votes
1 answer
300 views

Is there a planar 4-regular graph that is 3-acyclic colourable?

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours). Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
Cyriac Antony's user avatar
2 votes
1 answer
102 views

Producing colouring of maximal planar graphs G from colouring of dual of G

A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one ...
Cyriac Antony's user avatar
3 votes
2 answers
817 views

Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
Saeed's user avatar
  • 3,440
1 vote
1 answer
92 views

Reachability Query for Tree

What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $...
yefi's user avatar
  • 13
-1 votes
1 answer
78 views

the shorstest cycle containing two given points

I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
Mathieu Mari's user avatar
0 votes
1 answer
80 views

Reduction graph to planar bounded treewidth and bounded diameter graph

We got reduction graph to planar bounded treewidth graph, but this is unlikely to be true. Let $H$, the planarizing gadget, be planar graph with four distinguished vertices $u,u',v,v'$ on the outer ...
joro's user avatar
  • 1,955
7 votes
0 answers
181 views

Algebraic methods for testing planarity

Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
Will's user avatar
  • 215
9 votes
2 answers
557 views

NP-hardness of a planar SAT variant

Background: An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals. Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $...
squire's user avatar
  • 141
10 votes
1 answer
875 views

3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
Zach Hunter's user avatar
2 votes
2 answers
340 views

Representations of Planar Graphs in Coq

I would like to formalize some simple properties of planar graphs in the Coq proof assistant. 1) How are planar graphs formalized in the Coq proof assistant? Is there a "standard" definition that is ...
Springberg's user avatar
3 votes
0 answers
98 views

Algorithms for Maximum weight connected subgraph in planar graphs

I wonder what is known about the two following maximisation problems. Maximum weight connected subgraph : Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$ Output :...
Mathieu Mari's user avatar
3 votes
0 answers
75 views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles. Question: Is there some constant $k$ so that the $...
Elle Najt's user avatar
  • 1,469
0 votes
1 answer
116 views

Densest k subgraph problem for outerplanar graphs?

The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$. Does anyone know if there exists a polynomial-time ...
ChimiSeanGa's user avatar
0 votes
1 answer
94 views

Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
SamiD's user avatar
  • 2,319
2 votes
1 answer
94 views

Weighted Min-Cut in bounded-genus graphs

What is the status of the following decision problem ? Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$ Output : ...
Mathieu Mari's user avatar
2 votes
1 answer
182 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 ...
Elle Najt's user avatar
  • 1,469
7 votes
1 answer
363 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 ...
Mathieu Mari's user avatar