A compact adjacency-based topological data structure for finite element mesh representation

Waldemar Celes, Glaucio H. Paulino, Rodrigo Espinha

Research output: Contribution to journalArticlepeer-review

62 Scopus citations


This paper presents a novel compact adjacency-based topological data structure for finite element mesh representation. The proposed data structure is designed to support, under the same framework, both two- and three-dimensional meshes, with any type of elements defined by templates of ordered nodes. When compared to other proposals, our data structure reduces the required storage space while being 'complete', in the sense that it preserves the ability to retrieve all topological adjacency relationships in constant time or in time proportional to the number of retrieved entities. Element and node are the only entities explicitly represented. Other topological entities, which include facet, edge, and vertex, are implicitly represented. In order to simplify accessing topological adjacency relationships, we also define and implicitly represent oriented entities, associated to the use of facets, edges, and vertices by an element. All implicit entities are represented by concrete types, being handled as values, which avoid usual problems encountered in other reduced data structures when performing operations such as entity enumeration and attribute attachment. We also extend the data structure with the use of 'reverse indices', which improves performance for extracting adjacency relationships while maintaining storage space within reasonable limits. The data structure effectiveness is demonstrated by two different applications: for supporting fragmentation simulation and for supporting volume rendering algorithms.

Original languageEnglish (US)
Pages (from-to)1529-1556
Number of pages28
JournalInternational Journal for Numerical Methods in Engineering
Issue number11
StatePublished - Nov 21 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Numerical Analysis
  • General Engineering
  • Applied Mathematics


  • Finite element mesh
  • Implicit entities
  • Reduced representation
  • Topological data structure


Dive into the research topics of 'A compact adjacency-based topological data structure for finite element mesh representation'. Together they form a unique fingerprint.

Cite this