Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Crossing numbers of imbalanced graphs

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4n edges is at least constant times e³/n². Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d₁?d₂?···?d_n, then the crossing number satisfies \begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*} with \begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}, and that this bound is tight apart from the values of the constants c₁, c₂>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010     

Crossing minimization in weighted bipartite graphs

Given a bipartite graph G=(L₀,L₁,E) and a fixed ordering of the nodes in L₀, the problem of finding an ordering of the nodes in L₁ that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.     

Crossing minimization in extended level drawings of graphs

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles.In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings.We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.     

Crossing numbers of sequences of graphs II: Planar tiles

We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k‐crossing‐critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003     

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

The decompositions of line graphs,middle graphs and total graphs of complete graphs into forests

We construct decompositions of L(K_n), M(K_n) and T(K_n) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.     

Interior graphs of maximal outerplane graphs

A maximal outerplane graph (mop) is a plane embedding of a graph in which all vertices lie on the exterior face, and the addition of an edge between any two vertices would destroy this outerplanarity property. Removing the edges of the exterior face of a mop G results in the interior graph of G. We give a necessary and sufficient condition for a graph to be the interior graph of some mop.     

Crossing families

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least . As a consequence we show that such a set possesses a crossing family of size at least , and describe a fast algorithm for finding such a family.Research supported in part by DARPA grant N00014-89-J-1988, Air Force AFOSR-89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC8809648.     

Graph equations for line graphs,total graphs,middle graphs and quasi-total graphs

Let G be a graph with vertex-set V(G) and edge-set X(G). Let L(G) and T(G) denote the line graph and total graph of G. The middle graph M(G) of G is an intersection graph Ω(F) on the vertex-set V(G) of any graph G. Let F = V′(G) ∪ X(G) where V′(G) indicates the family of all one-point subsets of the set V(G), then $\text{M(G) = Ω(F)}$.The quasi-total graph P(G) of G is a graph with vertex-set V(G)∪X(G) and two vertices are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident to it in G.In this paper we solve graph equations $\text{L(G) ? P(H);}\text{L(G)}\text{? P(H); P(G) ? T(H);}\text{P(G)}\text{? T(H); M(G) ? P(H);}\text{M(G)}\text{? P(H)}$.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Universal graphs and induced-universal graphs

We construct graphs that contain all bounded-degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so-called universal graphs (or induced-universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced-universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced-universal graphs.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].