Abstracts


Dimitris Achlioptas (Invited Talk).
Algorithmic Barriers from Phase Transitions in Graphs

Abstract:
For a number of optimization problems on random graphs and hypergraphs, e.g., k-colorings, there is a very big gap between the largest average degree for which known polynomial-time algorithms can find solutions, and the largest average degree for which solutions provably exist. We study this phenomenon by examining how sets of solutions evolve as edges are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in the problem’s solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random instances our results provide novel constructions of one-way functions.


Erik Demaine
(Invited Talk).
Algorithmic Graph Minors and Bidimensionality

Abstract: Graph Minor Theory, developed by Robertson and Seymour over two decades, provides powerful structural results about a wide family of graph classes (anything closed under deletion and contraction). In recent years, this theory has been extended and generalized to apply to many algorithmic problems.  Bidimensionality theory is one approach to algorithmic graph minor theory.  This theory provides general tools for designing fast (constructive, often subexponential) fixed-parameter algorithms, kernelizations, and approximation algorithms (often PTASs), for a wide variety of NP-hard graph problems for graphs excluding a fixed minor.  For example, some of the most general algorithms for feedback vertex set and connected dominating set are based on bidimensionality.  Another approach is ``deletion and contraction decompositions'', which split any graph excluding a fixed minor into a bounded number of small-treewidth graphs.  For example, this approach has led to some of the most general algorithms for graph coloring and the Traveling Salesman Problem on graphs.  I will describe these and other approaches to efficient algorithms through graph minors.
 



Yota Otachi, Hans L. Bodlaender and Erik Jan van Leeuwen.
Complexity Results for the Spanning Tree Congestion Problem

Abstract:  We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k >= 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.


Marcin Kaminski.
Max-Cut and containment relations in graphs

Abstract:  We study (Simple) Max-Cut in classes of graphs defined by forbidding a single graph as a subgraph, induced subgraph, or minor. For the first two containment relations, we prove dichotomy theorems. For the minor order, we show how to solve Max-Cut in polynomial time for the class obtained by forbidding a graph with crossing number at most one (this generalizes a known result for K5-minor-free graphs) and identify an open problem which is the missing case for a dichotomy theorem.


Stavros Nikolopoulos and Kyriaki Ioannidou.
The Longest Path Problem is Polynomial on Cocomparability Graphs

Abstract:  The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago~\cite{Damasc92}, the complexity status of the longest path problem on cocomparability graphs has remained open until now; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs~\cite{Ioan-Mer-Nik09} and provides polynomial solution to the class of permutation graphs.


Petr Golovach, Dieter Kratsch and Jean-Francois Couturier.
Colorings With Few Colors: Counting, Enumeration and Combinatorial Bounds

Abstract:  Enumeration and counting problems on edge colorings, total colorings and $L(2,1)$-labelings of graphs are studied. The major part deals with the enumeration of three types of colorings with few colors: edge $3$-colorings, total $4$-colorings and the $L(2,1)$-labelings of span $5$ in connected cubic graphs. Branching algorithms to enumerate the colorings in connected cubic graphs are established. They imply upper bounds on the maximum number of colorings in any $n$-vertex connected cubic graphs. Lower bounds are also provided. Particularly, for edge $3$-colorings the following is achieved: there is a branching algorithm to enumerate all edge $3$-colorings of a connected cubic graph in time $O^*(2^{5n/8})$. This implies that the maximum number of edge $3$-colorings in an $n$-vertex connected cubic graph is $O^*(2^{5n/8})$.   Finally the maximum number of edge $3$-colorings in an $n$-vertex connected cubic graph is lower bounded by $12^{n/10}$. Dynamic programming algorithms to count the number of edge $k$-colorings and total $k$-colorings for graphs of bounded pathwidth are presented. We also provide a dynamic programming algorithm to count the number of $L(2,1)$-labelings of span $4$ for graphs of maximum degree three.


Tamas Fleiner.
On stable matchings and flows

Abstract:  We describe a flow model that generalizes ordinary network flows the same way as stable matchings generalize the bipartite matching problem. We prove that there always exists a stable flow, generalize the lattice structure of stable marriages to stable flows.


Hajo Broersma, Petr Golovach, Daniel Paulusma and Jian Song.
Narrowing down the gap on the complexity of coloring P_k-free graphs

Abstract:  A graph is P_k-free if it does not contain an induced subgraph isomorphic to a path on k vertices. We show that deciding whether a P_8-free graph can be colored with at most four colors is an NP-complete problem. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-coloring is NP-complete for P_9$-free graphs, and a result of Woeginger and Sgall, who showed that 5-coloring is NP-complete for P_8-free graphs. Additionally, we prove that the pre-coloring extension version of 4-coloring is NP-complete for P_7-free graphs, but that the pre-coloring extension version of 3-coloring is polynomially solvable for (P_4+P_2)-free graphs, a subclass of P_7-free graphs.


Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof.
Computing the cutwidth of bipartite permutation graphs in linear time

Abstract:  The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al.~initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth, and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs.


Mathieu Liedloff, Ioan Todinca and Yngve Villanger.
Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching

Abstract:  The Capacitated Dominating Set problem is the problem of finding a dominating set of minimum cardinality where each vertex has been assigned a bound on the number of vertices it has capacity to dominate. Cygan et al. showed in 2009 that this problem can be solved in $O(n^3 m {n \choose n/3})$ or in $O^*(1.89^n)$ time using maximum matching algorithm. An alternative way to solve this problem is to use dynamic programming over subsets. By exploiting structural properties of instances that can not be solved fast by the maximum matching approach, and "hiding" additional cost related to considering subsets of large cardinality in the dynamic programming, an improved algorithm is obtained. We show that the {\sc Capacitated Dominating Set} problem can be solved in $O^*(1.8463^n)$ time.


Frederic Dorn, Hannes Moser, Rolf Niedermeier and Mathias Weller.
Efficient Algorithms for Eulerian Extension

Abstract:  Eulerian extension problems aim at making a given (directed) (multi-)graph Eulerian by adding a minimum-cost set of edges (arcs). These problems have natural applications in scheduling and routing and are closely related to the CHINESE POSTMAN and RURAL POSTMAN problems. Our main result is to show that the NP-hard WEIGHTED MULTIGRAPH EULERIAN EXTENSION is fixed-parameter tractable with respect to the number k of extension edges (arcs). The corresponding running time amounts to 4^k * n^O(1). This implies a fixed-parameter tractability result for the "equivalent" RURAL POSTMAN problem. In addition, we develop several polynomial-time algorithms for natural Eulerian extension problems.


Ge Xia and Yong Zhang.
On the Small Cycle Transversal of Planar Graphs

Abstract:  We consider the problem of finding a $k$-edge transversal set that covers all (simple) cycles of length at most $s$ in a planar graph, where $s \geq 3$ is a constant. This problem, referred to as {\sc Small Cycle Transversal}, is known to be NP-complete. We present a polynomial-time algorithm that computes a linear kernel of size $36 s^3k$ for {\sc Small Cycle Transversal}. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. [J. ACM, 2004] by considering a {\em unique} region decomposition that is defined by shortest paths. Unlike the previous results on linear kernels of problems on planar graphs, our results are not subsumed by the recent meta-theorems on kernelization of~Bodlaender et al. [FOCS, 2009].


Panos Giannopoulos, Christian Knauer, Mike Fellows, Christophe Paul, Frances Rosamond, Sue Whitesides and Nathan Yu.
Milling a Graph with Turn Costs: a Parameterized Complexity Perspective

Abstract:  The Abstract Milling problem is a natural and quite general graph-theoretic model for geometric milling problems: Given a graph, one asks for a walk that covers all its vertices with a minimum number of turns, as specified in the graph model by a 0/1 turncost function f_{x} at each vertex x giving, for each ordered pair of edges (e,f) incident at x, the turn cost at x of a walk that enters the vertex on edge e and departs on edge f. We describe an initial study of the parameterized complexity of the problem.


Karin Arikushi, Radoslav Fulek, Balazs Keszegh, Filip Moric and Csaba Toth.
Drawing Graphs with Orthogonal Crossings

Abstract:  We consider {\em right angle crossing (RAC) drawings} of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with $n$ vertices admits an RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most $6.5n$ and $74.2n$, respectively. This is a strengthening of a recent result of Didimo {\em et al.}


Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Wojtaszczyk.
Kernelization hardness of connectivity problems in d-degenerate graphs

Abstract:  A graph is d-degenerate if its every subgraph contains a vertex of degree at most d. For instance, planar graphs are 5-degenerate. Inspired by recent work by Philip, Raman and Sikdar, who have shown the existence of a polynomial kernel for DOMINATING SET in d-degenerate graphs, we investigate kernelization hardness of problems that include connectivity requirement in this class of graphs. Our main contribution is the proof that CONNECTED DOMINATING SET does not admit a polynomial kernel in d-degenerate graphs for d >= 2 unless the polynomial hierarchy collapses up to the third level. We prove this by introducing a new problem — CONNECTED COLOURS — that nicely encapsulates the hardness of the connectivity requirement. We extend our analysis by showing that, unless PH = sigma_p^3, there do not exist polynomial kernels for STEINER TREE, CONNECTED FEEDBACK VERTEX SET and CONNECTED ODD CYCLE TRANSVERSAL in d-degenerate graphs for d >= 2. On the other hand, we show a polynomial kernel for CONNECTED VERTEX COVER in graphs that do not contain the biclique K(i,j) as a subgraph.


Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle and Martin Vatshelle.
On the boolean-width of a graph: structure and applications

Abstract:  Boolean-width is a recently introduced graph invariant. Similar to tree-width, it measures the structural complexity of graphs. Given any graph $G$ and a decomposition of $G$ of boolean-width $k$, we give algorithms solving a large class of vertex subset and vertex partitioning problems in time $O^*(2^{O(k^2)})$. We relate the boolean-width of a graph to its branch-width and to the boolean-width of its incidence graph. For this we use a constructive proof method that also allows much simpler proofs of similar results on rank-width by Oum (JGT 2008). For a random graph on $n$ vertices we show that almost surely its boolean-width is $\Theta(\log^2 n)$ -- setting boolean-width apart from other graph invariants -- and it is easy to find a decomposition witnessing this. Combining our results gives algorithms that on input a random graph on $n$ vertices will solve a large class of vertex subset and vertex partitioning problems in quasi-polynomial time $O^*(2^{O(\log ^4 n)})$.


Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul and Jan Arne Telle.
Generalized graph clustering: recognizing (p,q)-cluster graphs

Abstract:  Cluster Editing is a classical graph theoretic approach to tackle the problem of data set clustering: it consists of modifying a similarity graph into a disjoint union of cliques, i.e, clusters. As pointed out in a number of recent papers, the cluster editing model is too rigid to capture common features of real data sets. Several generalizations have thereby been proposed. In this paper, we introduce (p,q)-cluster graphs, where each cluster misses at most p edges to be a clique, and there are at most q edges between a cluster and other clusters. Our generalization is the first one that allows a large number of false positives and negatives in total, while bounding the number of these locally for each cluster by p and q. We show that recognizing (p,q)-cluster graphs is NP-complete when p and q are input. On the positive side, we show that (0,q)-cluster, (p,1)-cluster, (p,2)-cluster, and (1,3)-cluster graphs can be recognized in polynomial time.


Konrad Dabrowski, Vadim Lozin, Rajiv Raman and Bernard Ries.
Colouring vertices of triangle-free graphs

Abstract:  The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it remains NP-complete even if we additionally exclude a graph $F$ which is not a forest. We study the computational complexity of the problem in $(K_3, F)$-free graphs with $F$ being a forest. From known results it follows that for any forest $F$ on 5 vertices the vertex colouring problem is polynomial-time solvable in the class of $(K_3, F)$-free graphs. In the present paper, we show that the problem is also polynomial-time solvable in many classes of $(K_3, F)$-free graphs with $F$ being a forest on 6 vertices.


Geevarghese Philip, Venkatesh Raman and Yngve Villanger.
A Quartic Kernel for Pathwidth-One Vertex Deletion

Abstract:  The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k) where |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G has O(k^4) vertices, and (iii) k' ≤ k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O*(7^k · n^3) time. These figures compare favorably with the best results known for the closely related, and extensively studied, Feedback Vertex Set problem.


Jeremie Chalopin, Paola Flocchini, Bernard Mans and Nicola Santoro.
Network Exploration by Silent and Oblivious Robots

Abstract:  In this paper we investigate the basic problem of {\em Exploration} of a graph by a group of identical mobile computational entities, called robots, operating autonomously and asynchronously. In particular we are concerned with what graphs can be explored, and how, if the robots do not remember the past and have no explicit means of communication. This model of robots is used when the spatial universe in which the robots operate is {\em continuous} (e.g., a curve, a polygonal region, a plane, etc.). The case when the spatial universe is {\em discrete} (i.e., a graph) has been also studied but only for the classes of acyclic graphs and of simple cycles. In this paper we consider networks of arbitrary topology modeled as connected graphs with local orientation (locally distinct edge labels). We concentrate on class ${\cal H}_k$ of asymmetric configurations with $k$ robots. Our results indicate that the explorability of graphs in this class depends on the number $k$ of robots participating in the exploration. In particular, exploration is impossible for $k<3$ robots. When there are only $k=3$ robots, only a subset of ${\cal H}_3$ can be explored; we provide a complete characterization of the networks that can be explored, and present an exploration algorithm. When there are $k=4$ robots, we prove that all networks in ${\cal H}_4$ can be explored; the proof is constructive, and the algorithm is (unfortunately) quite involved. Finally, we prove that for any odd $k>4$ all networks in ${\cal H}_k$ can be explored by presenting a general algorithm. The determination of which networks can be explored when $k>4$ is even, is still open but can be reduced to the existence of a rendezvous algorithm for ${\cal H}_k$.


Annabell Berger and Matthias Müller-Hannemann.
Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence

Abstract:  Many applications in network analysis require algorithms to sample uniformly at random from the set of all graphs  with a prescribed degree sequence. We present a Markov chain based approach which converges to the uniform distribution of all realizations for both the directed and undirected case. It remains an open challenge whether these Markov chains are rapidly mixing. For the case of directed graphs, we also explain in this paper that a popular switching algorithm fails in general to sample uniformly at random because the state graph of the Markov chain decomposes into different isomorphic components. We call degree sequences for which the state graph is strongly connected arc swap sequences. To handle arbitrary degree sequences, we develop two different solutions. The first uses an additional operation (a reorientation of induced directed 3-cycles) which makes the state graph strongly connected, the second selects randomly one of the isomorphic components and samples inside it. Our main contribution is a precise characterization of arc swap sequences, leading to an efficient recognition algorithm. Finally, we point out some interesting consequences for network analysis.


René van Bevern, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier.
Measuring Indifference: Unit Interval Vertex Deletion

Abstract:  Making a graph unit interval by a minimum number of vertex deletions is NP-complete. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-parameter algorithm based on the iterative compression technique that finds in O((14k+14)^{k+1} k n^6) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval.


Dániel Marx and Ildikó Schlotter.
Parameterized Complexity of the Arc-Preserving Subsequence Problem

Abstract:  We study the Arc-Preserving Subsequence (APS) problem with unlimited annotations. Given two arc-annotated sequences P and T, this problem asks if it is possible to delete characters from T to obtain P. Since even the unary version of APS is NP-hard, we used the framework of parameterized complexity, focusing on a parameterization of this problem where the parameter is the number of deletions we can make. We present a linear-time FPT algorithm for a generalization of APS, applying techniques originally designed to give an FPT algorithm for Induced Subgraph Isomorphism on interval graphs.


Steven Chaplick, Marisa Gutierrez, Benjamin Lévêque and Silvia Tondato.
From path graphs to directed path graphs

Abstract:  We present a linear time algorithm to greedily orient the edges of  a path graph model to obtain a directed path graph model  (when possible). Moreover we extend this algorithm to find an odd sun  when the method fails. This algorithm has several interesting  consequences concerning the relationship between path graphs and  directed path graphs. One is that for a directed path graph,   path graph models and directed path graph models are the same. Another  consequence concerns the difference between path graphs and  directed path graphs in terms of forbidden induced subgraphs. This  can be used to deduce the forbidden induced subgraph  characterization of directed path graphs from the forbidden induced  subgraph characterization of path graphs. The last consequence is  algorithmic and shows that the recognition of directed path graphs  is not more difficult than the recognition of path graphs.


Nicolas Bonichon, Cyril Gavoille, nicolas hanusse and David ILCINKAS.
Connections between Theta-Graphs, Delaunay   Triangulations, and Orthogonal Surfaces

Abstract:  $\Theta_k$-graphs are geometric graphs that appear  in the context of graph navigation. The shortest-path metric of  these graphs is known to approximate the Euclidean complete graph  up to a factor depending on the cone number $k$ and the dimension of  the space.  TD-Delaunay graphs, a.k.a. triangular-distance Delaunay  triangulations introduced by Chew, have been shown to be plane  $2$-spanners of the 2D Euclidean complete graph, i.e., the distance  in the TD-Delaunay graph between any two points is no more than  twice the distance in the plane.  Orthogonal surfaces are geometric objects defined from independent  sets of points of the Euclidean space. Orthogonal surfaces are well  studied in combinatorics (orders, integer programming) and in  algebra. From orthogonal surfaces, geometric graphs, called geodesic  embeddings can be built.  In this paper, we introduce a specific subgraph of the $\TG$-graph  defined in the 2D Euclidean space, namely the $\DTG$-graph, composed  of the even-cone edges of the $\TG$-graph. Our main contribution is  to show that these graphs are exactly the TD-Delaunay graphs, and  are strongly connected to the geodesic embeddings of orthogonal  surfaces of coplanar points in the 3D Euclidean space.  Using these new bridges between these three fields, we establish:  - Every $\TG$-graph is the union of two spanning TD-Delaunay   graphs. In particular, $\TG$-graphs are $2$-spanners of the   Euclidean graph, and the bound of~$2$ on the stretch factor is   best possible. It was not known that $\Theta_6$-graphs are   $t$-spanners for some constant $t$, and $\Theta_7$-graphs were   only known to be $t$-spanners for $t \approx 7.562$.  - Every plane triangulation is TD-Delaunay realizable, i.e.,   every combinatorial plane graph for which all its interior faces are   triangles is the TD-Delaunay graph of some point set in the   plane. Such realizability property does not hold for classical   Delaunay triangulations.


Robert Elsaesser and Adrian Ogierman.
Efficient Broadcasting in Random Power Law Networks

Abstract:  In this paper, we consider the broadcasting problem in random power law graphs. For the underlying communication we use a simple modification of the so-called random phone call model introduced by Karp, Schindelhauer, Shenker, and V\"ocking (FOCS 2000). In the phone call model, every time step each node calls on a randomly chosen neighbor, and establishes a communication channel to this node. The communication channels can then be used to transmit messages in both directions. We show that if we allow every node to choose \textit{$\rho$ different neighbors} instead of one, where $\rho$ is some constant, then the average number of message transmissions per node decreases to an (almost) optimal value in certain random power law graphs. Formally, we present an algorithm that completes broadcasting in time $O(\log n)$ and uses $O(n \log\log n)$ transmissions per message, with probability $1-n^{-\Omega(1)}$, where $n$ is the size of the underlying network.


Padmini Mukkamala, Janos Pach and Deniz Sarioz.
Graphs with large obstacle numbers

Abstract:  Motivated by questions in computer vision and sensor networks, Alpert et al. introduced the following definitions. Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if an only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of G is the minimum number of obstacles in an obstacle representation of G. It was known that there exist graphs of n vertices with obstacle number at least sqrt(logn). We use extremal graph theoretic tools to show that (1) there exist graphs of n vertices with obstacle number at least n/(log n)^2, and (2) the total number of graphs on n vertices with bounded obstacle number is at most 2^{o(n^2)}. Better results are proved if we are allowed to use only convex obstacles or polygonal obstacles with a small number of sides.


Edyta Szymanska.
The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Codegree

Abstract:  In this note we consider the problem of deciding whether a given $r$-uniform hypergraph $H$ with minimum vertex degree at least $c|V(H)|$, has a vertex $2-$coloring and a strong vertex $k$-coloring. Motivated by an old result of Edwards for graphs, we summarize what can be deduced from his method about the complexity of these problems for hypergraphs. We obtain the first optimal dichotomy results for 2-colorings of 3- and 4-uniform hypergraphs. In addition, we determine the computational complexity of strong $k$-colorings of 3-uniform hypergraphs for some $c,$ leaving a gap which vanishes as $k\rightarrow \infty$.


Colin McDiarmid and Tobias Mueller.
The number of bits needed to represent a unit disk graph

Abstract:  We prove that for sufficiently large $n$, there exist unit disk graphs on $n$ vertices such that for every representation with disks in the plane at least $\gamma^{\sqrt{n}}$ bits are needed to write down the coordinates of the centers of the disks, for some $\gamma > 1$.


Jannik Matuschke and Britta Peis.
Lattices and maximum flow algorithms in planar graphs

Abstract:  We show that the left/right relation on the set of s-t-paths of a plane graph induces a so-called "submodular" lattice. If the embedding of the graph is s-t-planar, this lattice is even consecutive. This implies that Ford and Fulkerson's uppermost path algorithm for maximum flow in such graphs is indeed a special case of a two-phase greedy algorithm on lattice polyhedra. We also show that the properties submodularity and consecutivity cannot be achieved simultaneously by any partial order on the paths if the graph is planar but not s-t-planar, thus providing a characterization of this class of graphs.






Comments