# Graph Planarity by Replacing Cliques with Paths +
## 1 Introduction  
A typical problem concerning the visual analysis of real-world networks refers to the creation of occlusions and hairball-like structures in dense subnetworks when node-link diagrams are generated by standard layout algorithms, e.g., force-directed methods. On the other hand, different representations, such as adjacency matrices, are well suited for dense graphs but make neighbor identification and path-tracing more difficult [1; 2]. _Hybrid graph representations_ combine different visualization metaphors in order to exploit their strengths and overcome their drawbacks.  
The _NodeTrix_ model [3] represents a first example of hybrid representation. It combines node-link diagrams with adjacency-matrix representations of the denser subgraphs [3; 4; 5; 6]. Inspired by NodeTrix, other hybrid representation models were recently introduced [7; 8; 9]. The _ChordLink_ model [7] embeds chord diagrams, used for the visualization of dense subgraphs (_clusters_), into a node-link diagram. In a \((k,p)\)_representation_[8], each cluster contains at most \(k\) vertices and each vertex can occur at most \(p\) times along the boundary of the cluster. In the _intersection-link representations_[9] model, vertices are geometric objects and edges are either intersections between objects (_intersection-edges_) or crossing-free Jordan arcs attaching at their boundary (_link-edges_). Different types of objects determine different intersection-link representations.  
_Clique-planar_ drawings are defined in [9] as intersection-link representations in which the objects are isothetic rectangles, and the partition into intersection- and link-edges is given as a part of the input, so that the graph induced by the intersection-edges is composed of a set of vertex-disjoint cliques. The corresponding recognition problem, called Clique-planarity, has been proved NP-complete in general and polynomial-time solvable in restricted cases, for example when the rectangle representing each vertex is given as a part of the input, or when the cliques are arranged on levels according to a hierarchy. In [9], it is also proven that, if a graph is clique-planar, then it admits an intersection-link representation in which all vertices in a same cluster are isothetic unit squares whose upper-left corners are aligned along a line of slope one (see Figure 1a,b).  
Therefore, we can reformulate the Clique-planarity problem in the terminology of _beyond-planarity_[10; 11] as follows. Given a graph \(G=(V,E)\) and a partition of its vertex set \(V\) into subsets \(V_{1},\ldots,V_{m}\) such that the subgraph of \(G\) induced by each subset \(V_{i}\) is a clique, the goal is to compute a planar subgraph \(G^{\prime}=(V,E^{\prime})\) of \(G\) by replacing the clique induced by \(V_{i}\), for each \(i=1,\ldots,m\), with a path spanning the vertices of \(V_{i}\) (see Figure 1c).  
In this paper, we introduce and study a problem called _h_-Clique2 Path Planarity (for short, _h_-C2 PP), that is a restricted version of Clique-planarity in which the input graph comes with a given embedding and each clique has size at most \(h\). Preliminary results have been presented in [12].  
Figure 1: (**a**) A non-planar graph \(G\). Cliques are highlighted with bold edges. (**b**) A clique-planar drawing of \(G\). (**c**) Replacing each clique by a path spanning its vertices. Note that, different from (**a**), in (**c**), the first vertex and the last vertex of each path have only one place to connect to edges, while the interior vertices have two places: this is what makes the problem non-trivial.