We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithm due to Bouchitté and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices.

Abstract Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

Abstract We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance $$\delta$$ δ from each other. We investigate the complexity of this problem in terms of the rational parameter $$\delta$$ δ . The problem is polynomially solvable, if the numerator of $$\delta$$ δ is 1 or 2, while all other cases turn out to be NP-hard.

The status of a vertex v in a connected graph is the sum of the distances from v to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some new results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we show that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.

We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard.

Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.

In this article, we consider k‐way vertex cut: the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of components. Our main contribution is the derivation of an efficient polynomial‐time approximation scheme for the problem on planar graphs. Also, we show that k‐way vertex cut is polynomially solvable on graphs of bounded treewidth and fixed–parameter tractable on planar graphs with the size of the separator as the parameter. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 170–178 2014

To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak, these valves separate the system into a number of pieces, limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, of placing the valves in the network in such a way that the maximum possible spill, i.e., the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) series-parallel graphs, and hence graphs of treewidth two; and (ii) all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme for networks of bounded treewidth.

Abstract We address the algorithmic complexity of a profit maximization problem in capacitated, undirected networks. We are asked to price a set ofmcapacitated network links to serve a set ofnpotential customers. Each customer is interested in purchasing a network connection that is specified by a simple path in the network and has a maximum budget that we assume to be known to the seller. The goal is to decide which customers to serve, and to determine prices for all network links in order to maximize the total profit. We address this pricing problem in different network topologies. More specifically, we derive several results on the algorithmic complexity of this profit maximization problem, given that the network is either a path, a cycle, a tree, or a grid. Our results include approximation algorithms as well as inapproximability results. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs.

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of k-outerplanar graphs the running time becomes O(n3). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.