Using bigraphs to model topological graphs embedded in orientable surfaces

作者：Worboys M F^*

来源：Theoretical Computer Science, 2013, 484: 56-69.

DOI：10.1016/j.tcs.2013.02.018

• Bigraph
• Combinatorial map
• Spatial modeling
• Graph embedding

Natural and artificial environments, at scales ranging from cellular to geographic, have complex and changing spatial structures based on regions, as well as being inhabited by a multiplicity of dynamic entities. Milner's theory of bigraphs provides a formal design tool for dynamic and complex systems. However, bigraphs have rather limited explicit capability to represent spatial properties and relationships, being only equipped with a place graph that can express the containment relation between locations. This paper develops constructions that provide explicit bigraph types for representing complex two-dimensional spatial configurations, and shows that such representations are unique up to topological equivalence. In particular, we show how bigraphs can uniquely represent topological graphs embedded in compact, orientable surfaces in R-n, as well as in the Euclidean plane.

• 出版日期2013-5-6