Concept

Branch-decomposition

Related publications (7)

Simple Realizability of Complete Abstract Topological Graphs Simplified

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

SPRINGER2020

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

Signal-Adapted Tight Frames on Graphs

Dimitri Nestor Alice Van De Ville, Hamid Behjat

The analysis of signals on complex topologies modeled by graphs is a topic of increasing importance. Decompositions play a crucial role in the representation and processing of such information. Here, we propose a new tight frame design that is adapted to a ...

Institute of Electrical and Electronics Engineers2016

THE NUMBER OF EDGES IN k-QUASI-PLANAR GRAPHS

János Pach

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...

SIAM Publications2013

Decomposition and tractability in qualitative spatial and temporal reasoning

Jingshi Li

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...

Elsevier2013

Simultaneous Point Matching and 3D Deformable Surface Reconstruction

Pascal Fua, Appu Shaji, Aydin Varol

It has been shown that the 3D shape of a deformable surface in an image can be recovered by establishing correspondences between that image and a reference one in which the shape is known. These matches can then be used to set-up a convex optimization prob ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2010

Polarity of chordal graphs

Dominique de Werra, Tinaz Ekim

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...

2008