Relating planar graph drawings to planar satisfiability problems

Abstract

A graph G(V, E) consists of a set of vertices V and a set of edges E, where every edge e ∈ E makes a relationship between two vertices. Graph theory has numerous applications in computer networks, information systems, software engineering, VLSI design, social net- work, etc. Many real-life problems are being solved by simulating them into graph problems. Graphs Drawing is one of the famous fields of graph theory that is vastly used for information visualization. Among different graph drawing techniques, orthogonal drawing, orthogonally convex drawing, rectangular drawing, box-rectangular drawing, box-orthogonal drawing, bus drawing, bar visibility drawing, etc. cover a wide area and attracted researchers because of their aesthetic drawing properties. This thesis relates planar graph drawings to planar sat- isfiability problems. The satisfiability (SAT) problem is the first NP-complete problem in the theory of computation (Cook-Levin theorem). A SAT graph G(Φ) of a satisfiability instance Φ consists of a vertex for each clause and a vertex for each variable, where there exists an edge between a clause vertex and a variable vertex if and only if the variable or its negation appears in that clause. Many satisfiability problems, which are NP-hard in general, become polynomial-time solvable when the SAT graph is restricted to satisfy some graph properties. A rich body of research attempts to narrow down the boundary between the NP-hardness and polynomial-time solvability of various satisfiability problems. Beside that, many restricted classes of SATs may exist that are NP-hard but not proven yet. A 3-SAT problem is called positive and planar if all the literals are positive and the clause-variable incidence graph (i.e., SAT graph) is planar. The NAE 3-SAT and 1-in-3-SAT are two variants of 3-SAT that re- main NP-complete even when they are positive. The positive 1-in-3-SAT problem remains NP-complete under planarity constraint, but planar NAE 3-SAT is solvable in O(n1.5 log n) time, where n is the number of vertices. In this thesis, we prove that a positive planar NAE

xiv

Abstract xv 3-SAT is always satisfiable when the underlying SAT graph is 3-connected, and a satisfiable assignment can be obtained in linear time. Additionally, we show that without 3-connectivity constraint, the existence of a linear-time algorithm for a positive planar NAE 3-SAT prob- lem is unlikely as it would imply a linear-time algorithm for finding a spanning 2-matching in a planar subcubic graph. We also prove that positive planar 3-connected 1-in-3-SAT is computationally hard even if every variable presents in at most 4 clauses, whereas we show that 3-connected planar 1-in-3-SAT is always satisfiable when each variable appears in an even number of clauses. In this thesis, we also examine planar satisfiability problems and leverage planar graph drawing algorithms to improve our understanding of these problems. A rich body of graph drawing algorithms exists to check whether a planar graph admits a drawing that satisfies certain drawing aesthetics. We show how the existing graph draw- ing knowledge could be used to establish sufficient conditions for a SAT instance to always be satisfiable and give algorithms to efficiently find a satisfying truth assignment. In some cases, our algorithm can find a truth assignment by setting a small number of variables to true, which relates to the satisfiability variants that seek to minimize the number of ones. As byproducts in our research, we give the following results. (A) The first necessary and suffi- cient condition for a planar graph with the maximum degree 3 to admit a no-bend orthogonal drawing. Our condition leads to a linear-time algorithm to find such a drawing if it exists. (B) A necessary and sufficient condition for a subdivision of a triconnected cubic planar graph to admit a no-bend orthogonally convex drawing and design a linear-time algorithm to check the condition and to compute a desired drawing, if it exists. Additionally, we show that if a subdivision of a triconnected cubic planar graph G admits a rectilinear drawing, then it must also admit a rectilinear drawing with orthogonally convex faces. In this thesis, we also introduce a “sliding column model” for t-unit bar visibility representation of a graph and show that every graph G of maximum degree ∆ has a t-unit bar visibility representation for t ≤ ⌊∆+1 ⌋. If G is a simple graph of n vertices of even degree and m edges, and if G has no isolated vertex, then G has a t-unit bar visibility representation on at most m/3 columns for t = ∆/2. If G has some odd degree vertices, then G has a t-unit bar visibility representation R for t ≤ ⌊∆+1 ⌋, and R requires some additional columns depending on the necessity of some dummy edges in G required for obtaining an Eulerian circuit. We show that a planar

Abstract xvi graph of maximum degree 3 having n vertices and m edges has a 2-unit bar visibility repre- sentation on 2n − m columns and a 3-connected cubic graph of n vertices admits a 2-unit bar visibility representation on n columns.