Concept

Outerplanar graph

Related publications (90)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors

Bartosz Maria Walczak

Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number Θ(log log n). ...

2013

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

Efficient graph planarization in sensor networks and local routing algorithm

Florian Huc

In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under ligh ...

Ieee2012

Tangled Thrackles

János Pach

A tangle is a graph drawn in the plane so that any pair of edges have precisely one point in common, and this point is either an endpoint or a point of tangency. If we allow a third option: the common point may be a proper crossing between the two edges, t ...

Springer Berlin Heidelberg2012

Coloring K-k-free intersection graphs of geometric objects in the plane

János Pach

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-f ...

2012

Robust Non-Rigid Registration of 2D and 3D Graphs

Pascal Fua, Jan Kybic, Przemyslaw Rafal Glowacki

We present a new approach to matching graphs embedded in R2 or R3. Unlike earlier methods, our approach does not rely on the similarity of local appearance features, does not require an initial alignment, can handle partial matches, and can cope with non-l ...

2012

Learning of Structured Graph Dictionaries

Pascal Frossard, Xiaowen Dong, Xue Zhang

We propose a method for learning dictionaries towards sparse approximation of signals defined on vertices of arbitrary graphs. Dictionaries are expected to describe effectively the main spatial and spectral components of the signals of interest, so that th ...

2012

Locating the Source of Diffusion in Large-Scale Networks

Martin Vetterli, Patrick Thiran, Pedro Pereira Correia Pinto

How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks---such as the Internet or the human social graph---it is usually infeasible to observe the state of all nodes in a network. We show that it i ...

American Physical Society2012

Are motorways rational from slime mould's point of view ?

Emanuele Strano

We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, I ...

2012

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011