Skip navigation

Using bigraphs to model topological graphs embedded in orientable surfaces

Using bigraphs to model topological graphs embedded in orientable surfaces

Worboys, M.F. (2013) Using bigraphs to model topological graphs embedded in orientable surfaces. Theoretical Computer Science, 484. pp. 56-69. ISSN 0304-3975 (doi:https://doi.org/10.1016/j.tcs.2013.02.018)

Full text not available from this repository. (Request a copy)

Abstract

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 ℜn, as well as in the Euclidean plane. © 2013 Elsevier B.V.

Item Type: Article
Additional Information: [1] First published: 6 May 2013. [2] Published as: Theoretical Computer Science, (2013), Vol. 484, pp. 56–69.
Uncontrolled Keywords: bigraph, combinatorial map, spatial modeling, graph embedding
Subjects: Q Science > QA Mathematics
Faculty / Department / Research Group: Faculty of Liberal Arts & Sciences
Faculty of Liberal Arts & Sciences > Department of Computing & Information Systems
Last Modified: 20 Sep 2019 11:50
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/10088

Actions (login required)

View Item View Item