Search

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph G is a graph that admits a representation where its vertices correspond to paths in a grid Q, such that two vertices of G are adjacent if and only if their corresponding paths in Q have a common edge. If the paths in the representation have at most k bends, we say that it is a Bk-EPG representation. A collection C of sets satisfies the Helly property when every sub-collection of C that is pairwise intersecting has at least one common element. In this paper, we show that given a graph G and an integer k, the problem of determining whether G admits a Bk-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-Bk-EPG representation, is in NP, for every k bounded by a polynomial function of jV (G)j. Moreover, we show that the problem of recognizing Helly-B1-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs. [ABSTRACT FROM AUTHOR]

A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges ( → B 1 -EPG); (ii) the paths on the grid are not bended and the intersections concern vertices ( → B 0 -VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B 1 -EPG cographs and B 0 -VPG cographs using their cotree. [ABSTRACT FROM AUTHOR]

Abstract: We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most k bends (turns). We call such a subclass the -VPG graphs, . We present a complete hierarchy of VPG graphs relating them to other known families of graphs. String graphs are equivalent to VPG graphs. The grid intersection graphs [S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka, S. Whitesides, Grid intersection graphs and boxicity, Discrete Math. 114, (1993), 41–49; I. Ben-Arroyo Hartman, I. Newman, R. Ziv, On grid intersection graphs, Discrete Math. 87(1), (1991), 41–52] are shown to be equivalent to the bipartite -VPG graphs. Chordal -VPG graphs are shown to be exactly Strongly Chordal -VPG graphs. We prove the strict containment of -VPG and circle graphs into -VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are -VPG graphs. In the case of -VPG graphs, we observe that a set of horizontal and vertical segments have strong Helly number 2. We show that the coloring problem for -VPG graphs, for , is NP-complete and give a 2-approximation algorithm for coloring -VPG graphs. Furthermore, we prove that triangle-free -VPG graphs are 4-colorable, and this is best possible. [Copyright &y& Elsevier]

A graph G =(V,E) is a chordal probe graph if its vertices can be partitioned into two sets, P (probes) and N (non-probes), where N is a stable set and such that G can be extended to a chordal graph by adding edges between non-probes. We give several characterizations of chordal probe graphs, first, in the case of a ?xed given partition of the vertices into probes and non-probes, and second, in the more general case where no partition is given. In both of these cases, our results are obtained by introducing new classes, namely, N-triangulatable graphs and cycle-bicolorable graphs. We give polynomial time recognition algorithms for each class. N-triangulatable graphs have properties similar to chordal graphs, and we characterize them using graph separators and using a vertex elimination ordering. For cycle-bicolorable graphs, which are shown to be perfect, we prove that any cycle-bicoloring of a graph renders it N-triangulatable. The corresponding recognition complexity for chordal probe graphs, given a partition of the vertices into probes and non-probes, is O(|P||E|), thus also providing an interesting tractable subcase of the chordal graph sandwich problem. If no partition is given in advance, the complexity of our recognition algorithm is O(|E|²). [ABSTRACT FROM AUTHOR]

Abstract: An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195–198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131–153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality. For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read function and a read formula for F can be obtained in polynomial time. [Copyright &y& Elsevier]

Abstract: In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P 4-free. We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2 k function and a read 2 k formula for F for f can be obtained in polynomial time. [Copyright &y& Elsevier]

Abstract: Factoring Boolean functions is one of the basic operations in algorithmic logic synthesis. Current algorithms for factoring Boolean functions are based on some kind of division (Boolean or algebraic). In this paper, we present an algorithm for factoring that uses graph partitioning rather than division. Our algorithm is recursive and operates on the function and on its dual, to obtain the better factored form. As a special class, which appears in the lower levels of the factoring process, we handle read-once functions separately, as a special purpose subroutine which is known to be optimal. Since obtaining an optimal (shortest length) factorization for an arbitrary Boolean function is an NP-hard problem, all practical algorithms for factoring are heuristic and provide a correct, logically equivalent formula, but not necessarily a minimal length solution. Our method has been implemented in the SIS environment, and an empirical evaluation indicates that we usually get significantly better factorizations than algebraic factoring and are quite competitive with Boolean factoring but with lower computation costs. [Copyright &y& Elsevier]