In 1977, David Lichtenstein introduced in his master thesis [Lic77] the concept of planar
Boolean formulas. It was not until 1982 that his idea was first published in a journal [Lic82] …

The problem remains hard for monotone formulas, as well as for instances with exactly three
distinct variables per clause. In the course of this investigation, we show that monotone …

We consider the situation in which group activities need to be organized for a set of agents
when each agent can take part in at most one activity. The agents' preferences depend both …

The prominent Boolean formula satisfiability problem SAT is known to be 𝒩 𝒫-complete
even for very restricted variants such as 3-SAT, Monotone 3-SAT, or Planar 3-SAT, or …

We study a problem motivated by rectilinear schematization of geographic maps. Given a
biconnected plane graph G and an integer k≥ 0, does G have a strict-orthogonal drawing …

We survey variants of the Boolean Satisfiability problem from over the years and organize
them in what we believe to be the most comprehensive list of known results in SAT variants …

Let P be a polygon with r> 0 reflex vertices and possibly with holes and islands (ie,
components of the polygon inside holes). A subsuming polygon of P is a polygon P′ such …

Fire Emblem (FE) is a popular turn-based tactical role-playing game (TRPG) series on the
Nintendo gaming consoles. This paper studies the computational complexity of a simplified …

We address the problem of reconstructing a polygon from the multiset of its edges. Given n
line segments in the plane, find a polygon with n vertices whose edges are these segments …