Home
Lectures
Relating Planar Graph Drawings to Planar Satisfiability Problems

Relating Planar Graph Drawings to Planar Satisfiability Problems

Speaker: Md. Saidur Rahman – Dhaka, Bangladesh
Topic(s): Computational Theory, Algorithms and Mathematics

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 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.

About this Lecture

Number of Slides: 70
Duration: 50 minutes
Languages Available: English
Last Updated:

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.