Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Convex bipartite graph
Summary
In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties.
A bipartite graph, (U ∪ V, E), is said to be convex over the vertex set U if U can be enumerated such that for all v ∈ V the vertices adjacent to v are consecutive.
Convexity over V is defined analogously. A bipartite graph (U ∪ V, E) that is convex over both U and V is said to be biconvex or doubly convex.
Let G = (U ∪ V, E) be a bipartite graph, i.e., the vertex set is U ∪ V where U ∩ V = ∅.
Let NG(v) denote the neighborhood of a vertex v ∈ V.
The graph G is convex over U if and only if there exists a bijective mapping, f: U → {1, ..., |U|}, such that for all v ∈ V,
for any two vertices x,y ∈ NG(v) ⊆ U there does not exist a z ∉ NG(v) such that f(x) < f(z) < f(y).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.